package com.dmall.sort.algorithm;

/**
 * 插入排序
 * @author xiao1.wang
 * @date 2021/10/7 20:21
 */
@SuppressWarnings("all")
public class InsertionSort implements Sort {

    @Override
    public void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // insertionSort(arr, 0, arr.length - 1);
        insertionSort(arr, arr.length);
    }

    private void insertionSort(int[] arr, int n) {
        for (int i = 1; i < n; i++) {
            int value = arr[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (arr[j] > value) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = value;
        }
    }

    /**
     * 对指定范围[l, r]的数据进行插入排序
     * @param arr 待排序的数组
     * @param l 左区间索引
     * @param r 右区间索引
     */
    public static void insertionSort(int[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            int e = arr[i];
            int j;
            for (j = i; j > l && arr[j - 1] > e; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = e;
        }
    }

    @Override
    public String getName() {
        return "插入排序";
    }
}
